package src.backtracking_algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @author starsea
 * @date 2024-08-21 15:30
 */

public class Test05 {
    public static void main(String[] args) {
        String S = "qwe";
        String[] aa=permutation(S);

    }
   static List<String> ret = new ArrayList<>();
    static StringBuffer path = new StringBuffer();
    static int n;
    static boolean[] check;

    public static String[] permutation(String S) {
        n = S.length();
        check=new boolean[n];
        dfs(S);
        return ret.toArray(new String[ret.size()]);
    }

    public static void dfs(String str) {
        if (path.length()==n) {
            ret.add(path.toString());
            return;
        }
        for (int i =0; i < n; i++) {
            if(check[i]==false) {
                if (i == 0 || (i != 0 && str.charAt(i) != str.charAt(i - 1))) {
                    path.append(str.charAt(i));
                    check[i] = true;
                    dfs(str);
                    path.deleteCharAt(path.length() - 1);
                    check[i] = false;
                }
            }
        }
    }
}
